//你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources,
// targets。 
//
// 要完成第 i 个替换操作: 
//
// 
// 检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。 
// 如果没有出现， 什么也不做 。 
// 如果出现，则用 targets[i] 替换 该子字符串。 
// 
//
// 例如，如果 s = "abcd" ， indices[i] = 0 , sources[i] = "ab"， targets[i] = "eee" ，那么
//替换的结果将是 "eeecd" 。 
//
// 所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。 
//
// 
// 例如，一个 s = "abc" ， indices = [0,1] ， sources = ["ab"，"bc"] 的测试用例将不会生成，因为 "ab" 
//和 "bc" 替换重叠。 
// 
//
// 在对 s 执行所有替换操作后返回 结果字符串 。 
//
// 子字符串 是字符串中连续的字符序列。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：s = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
//
//输出："eeebffff"
//解释：
//"a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
//"cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。
// 
//
// 示例 2： 
//
// 
//输入：s = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee",
//"ffff"]
//输出："eeecd"
//解释：
//"ab" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
//"ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// k == indices.length == sources.length == targets.length 
// 1 <= k <= 100 
// 0 <= indexes[i] < s.length 
// 1 <= sources[i].length, targets[i].length <= 50 
// s 仅由小写英文字母组成 
// sources[i] 和 targets[i] 仅由小写英文字母组成 
// 
//
// Related Topics 数组 字符串 排序 👍 89 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author ldltd
 * @date 2023-08-15 00:37:56
 * @description 833.字符串中的查找与替换
 */
public class FindAndReplaceInString{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new FindAndReplaceInString().new Solution();
		 String s = "abcd";
		 int[]indices = {0,2};
		 String[] sources ={"a","cd"}, targets = {"eee","ffff"};
		 System.out.println(solution.findReplaceString(s, indices, sources, targets));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
		int offset=0;
		StringBuffer str = new StringBuffer(s);
		List<Integer> ops = new ArrayList<>();
		for (int i = 0; i < indices.length; i++) {
			ops.add(i);
		}
		//stream流，太慢
		// LinkedList<Integer> ops = IntStream.range(0, indices.length).boxed().sorted(Comparator.comparingInt(i -> indices[i])).collect(LinkedList::new, LinkedList::add, LinkedList::addAll);
		ops.sort((i, j) -> indices[i] - indices[j]);
		for (int i = 0; i < indices.length; i++) {
			int t=ops.get(i);
			if(s.substring(indices[t]).startsWith(sources[t])){
				str.replace(offset+indices[t],indices[t]+offset+sources[t].length(),targets[t]);
				offset+=targets[t].length()-sources[t].length();
			}
		}
		return str.toString();
	}
	/*hash表*/
	public String findReplaceString1(String s, int[] indices, String[] sources, String[] targets) {
		int n = s.length(), m = indices.length;

		Map<Integer, List<Integer>> ops = new HashMap<Integer, List<Integer>>();
		//我们只需要对数组 indices进行一次遍历，就可以得到这个哈希表。
		//在这之后，当我们对字符串 s 进行遍历时，如果遍历到位置 i，那么哈希表中键 i 对应的数组，就是所有对位置 iii 进行的操作

		for (int i = 0; i < m; ++i) {
			ops.putIfAbsent(indices[i], new ArrayList<Integer>());
			ops.get(indices[i]).add(i);
		}
		StringBuilder ans = new StringBuilder();
		for (int i = 0; i < n;) {
			boolean succeed = false;
			if (ops.containsKey(i)) {
				for (int pt : ops.get(i)) {
					if (s.substring(i, Math.min(i + sources[pt].length(), n)).equals(sources[pt])) {
						succeed = true;
						ans.append(targets[pt]);
						i += sources[pt].length();
						break;
					}
				}
			}
			if (!succeed) {
				ans.append(s.charAt(i));
				++i;
			}
		}
		return ans.toString();

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
